2.5 KB · ⤓ Micron 2.5 KB · ⤓ HTML 5.8 KB

layout: Wide · Narrow · Centered

top

Query complexity in computational complexity describes the number of queries needed to solve a computational problem for an input that can be accessed only through queries. See in particular:

• Aanderaa–Karp–Rosenberg conjecture, on the query complexity of graph problems accessed by querying the existence of edges

• Property testing, the study of query complexity for distinguishing objects having a property from objects far from having it

• Probabilistically checkable proof, a proof that can be verified by making a small number of queries to the bits of the proof

• Quantum complexity theory#Quantum query complexity, the number of queries needed to solve a problem using a quantum algorithm

• Query complexity in the decision tree model, the number of queries needed to solve a computational problem by an algorithm that is restricted to take the form of a decision tree

• Decision tree model#Quantum decision tree, decision tree complexity for a quantum decision tree

• Equitable cake-cutting#Query complexity, the number of times one must query participant preferences in a fair sharing procedure

• Query complexity in database theory, the complexity of evaluating a query on a database when measured as a function of the query size

• Query (complexity), a mapping between logical structures in descriptive complexity